package com.squirrel.michale;

import java.util.*;

/**
 * @author guanhao 观浩
 * @version 1.0.0.0
 * @createTime 2023/3/5 6:35 PM
 * @company Michale Squirrel
 * @link
 * @description
 */
public class LeetCode2121 {

    /*
            2 [0,4]
            1 [1,3]
            3 [2,5,6]
            result[element-1] = sum |num[i-1] - num[k]| k = 0,1,2,....,i-1
                               +sum |num[i-1] - num[k]| k = i,i+1,.....,n-1
            result[element] =  sum |num[i] - num[k]| k = 0,1,2,....,i
                              +sum |num[i] - num[k]| k = i,i+1,.....,n-1
            result[element] - result[element - 1] = (num[i] - num[i - 1]) * i + (num[i] - num[i - 1]) * (n - i);
                                                  = (num[i] - num[i - 1])* (2i- n)
*/


    public long[] getDistances(int[] arr) {
        int length = arr.length;
        Map<Integer, List<Integer>> hashMap = new HashMap<>();
        for (int i = 0; i < length; i++) {
            hashMap.computeIfAbsent(arr[i], k -> new ArrayList<>()).add(i);
        }
        long[] result = new long[length];
        for (List<Integer> indexList : hashMap.values()) {
            int n = indexList.size();
            long sum = 0;
            for (int i = 0; i < n; i++) {
                sum += indexList.get(i) - indexList.get(0);
            }
            result[indexList.get(0)] = sum;
            for (int i = 1; i < n; i++) {
                sum += (2L * i - n) * (indexList.get(i) - indexList.get(i - 1));
                result[indexList.get(i)] = sum;
            }
        }
        return result;
    }

    public long[] getDistances2(int[] arr) {
        Map<Integer, ArrayList<Integer>> hashMap = new HashMap<>();
        int length = arr.length;
        for (int i = 0; i < length; i++) {
            hashMap.computeIfAbsent(arr[i], k -> new ArrayList<>()).add(i);
        }

        long[] result = new long[length];
        for (Integer value : hashMap.keySet()) {
            ArrayList<Integer> indexList = hashMap.get(value);
            int n = indexList.size();
            long sum = 0;
            for (int i = 0; i < n; i++) {
                sum += indexList.get(i) - indexList.get(0);
            }
            // 因为hashMap 里ArrayList<Integer>保存了index的全集，所以可以用hashMap.get(value).get(i)获取到原始的下标，且不会遗漏。
            result[hashMap.get(value).get(0)] = sum;
            for (int i = 1; i < n; i++) {
                sum += (indexList.get(i) - indexList.get(i - 1)) * (2L * i - n);
                result[hashMap.get(value).get(i)] = sum;
            }
        }
        return result;
    }

    public long[] getDistances3(int[] arr) {
        Map<Integer, ArrayList<Integer>> hashMap = new HashMap<>();
        for (int i = 0; i < arr.length; i++) {
            ArrayList<Integer> orDefault = hashMap.getOrDefault(arr[i], new ArrayList<Integer>());
            orDefault.add(i);
            hashMap.put(arr[i], orDefault);
        }
        Map<Integer, ArrayList<Long>> resultMap = new HashMap<>();

        for (Integer value : hashMap.keySet()) {
            ArrayList<Integer> indexList = hashMap.get(value);
            int n = indexList.size();
            long sum = 0;
            for (int i = 0; i < indexList.size(); i++) {
                sum += indexList.get(i) - indexList.get(0);
            }
            ArrayList<Long> orDefault = resultMap.getOrDefault(value, new ArrayList<Long>());
            orDefault.add(sum);
            resultMap.put(value, orDefault);

            for (int i = 1; i < indexList.size(); i++) {
                sum += (long) (indexList.get(i) - indexList.get(i - 1)) * i;
                sum -= (long) (indexList.get(i) - indexList.get(i - 1)) * (n - i);
                ArrayList<Long> orDefault2 = resultMap.getOrDefault(value, new ArrayList<Long>());
                orDefault2.add(sum);
                resultMap.put(value, orDefault2);
            }
        }

        Map<Integer, Integer> alreadyPut = new HashMap<>();
        long[] result = new long[arr.length];
        for (int i = 0; i < arr.length; i++) {
            int already = alreadyPut.getOrDefault(arr[i], 0);
            result[i] = resultMap.get(arr[i]).get(already);
            alreadyPut.put(arr[i], already + 1);
        }
        return result;
    }

    public static void main(String[] args) {
        LeetCode2121 leetCode2121 = new LeetCode2121();
        int[] arr = new int[]{2, 1, 3, 1, 2, 3, 3};
        //[4,2,7,2,4,4,5]
        System.out.println(Arrays.toString(leetCode2121.getDistances(arr)));
    }
}
